#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#define maxn 1000
using namespace std;
int T, M;
int cost[maxn], val[maxn], dp[maxn][maxn], f[maxn];
/**
 *  dp[i,j]表示在容量为i的情况下,从1...j这些物品中的最优解
 *  dp[i,j] = max{dp[i,j-1],dp[i-cost[j],j-1]+val[j]};
 *  
 *  (1,1)...            (1,j)...               (1,m)
 *    .                   .                      .
 *    .       {i',j-1}    .                      .
 *    .                   .                      .
 *  (i,1)...  {i,j-1}   (i,j)...               (i,m)
 *    .                   .                      .
 *    .                   .                      .
 *    .                   .                      .
 *  (n,1)...            (n,j)...               (n,m)
 * 
 *  考虑对二维数组的压缩,只保留容量i作为数组下标
 *  新的数组记为 f[i],表示在容量为i的情况下从1...M中取得的最优解。
 *  1...i'...i...n
 *  在同样的循环中,将递推式改成:
 *  f[i] = max{f[i],f[i-cost[j]]+val[j]}
 * 
 * 
Test input:
    4 4
    1 2
    2 3
    3 3
    4 1
Expect:
    5
 * */
int main()
{
    cin >> T >> M;
    for (int i = 1; i <= M; ++i)
    {
        cin >> cost[i] >> val[i];
    }
    for (int j = 1; j <= M; j++)
    {
        for (int i = 1; i <= T; i++)
        {
            dp[i][j] = dp[i][j - 1];
            if (i >= cost[j])
            {
                dp[i][j] = max(dp[i][j - 1], dp[i - cost[j]][j - 1] + val[j]);
            }
        }
    }
    for (int j = 1; j <= M; j++)
    {
        for (int i = T; i >= cost[j]; i--)
        {
            if (i >= cost[j])
            {
                f[i] = max(f[i], f[i - cost[j]] + val[j]);
            }
        }
    }
    for (int i = 1; i <= T; i++)
    {
        printf("\n容量为:%d\t",i);
        for (int j = 1; j <= M; j++)
        {
            printf("(%d)\t", dp[i][j]);
        }
        printf("\tf:%d", f[i]);
    }
    return 0;
};